#include <stdio.h>

#define MAX_VAR_NUM 100
#define MAX_INT 0xffffffff

typedef struct {
    int vex_num;
    int adj_mat[MAX_VAR_NUM][MAX_VAR_NUM];
}Graph;

void GetGraph(Graph *g);
void Dijkstra(Graph *g, int v_0, unsigned int p[][MAX_VAR_NUM], unsigned int dist[]);

int main()
{
    Graph g;
    int v_0;
    unsigned int p[MAX_VAR_NUM][MAX_VAR_NUM];
    unsigned int dist[MAX_VAR_NUM];

    GetGraph(&g);
    scanf("%d", &v_0);
    Dijkstra(&g, v_0, p, dist);

    
    return 0;
}

void GetGraph(Graph *g)
{
    int i, j;
    scanf("%d", &g->vex_num);
    for (i = 0; i < g->vex_num; i++) {
        for (j = 0; j < g->vex_num; j++) {
            scanf("%d", &g->adj_mat[i][j]);
        }
    }
    return;
}

void Dijkstra(Graph *g, int v_0, unsigned int p[][MAX_VAR_NUM], unsigned int dist[])
{
    int finish[MAX_VAR_NUM];
    int v, w, i, j, min;

    for (v = 0; v < g->vex_num; v++) {
        finish[i] = 0;
        dist[v] = g->adj_mat[v_0][v];
        for (w = 0; w < g->vex_num; w++) {
            p[v][w] = 0;
        }
        if (dist[v] != 0) {
            p[v][v_0] = 1;
            p[v][v] = 1;
        } else {
            dist[v] = MAX_INT;
        }
    }
    
    finish[v_0] = 1;
    dist[v_0] = 0;

    for (i = 0; i < g->vex_num; i++) {
        min = MAX_INT;
        /* find the node with min dist */
        for (w = 0; w < g->vex_num; w++) {
            if (!finish[w] && dist[w] < min) {
                min = dist[w];
                v = w;  // the node with min dist
            }
        }

        finish[v] = 1; // add v into finish

        /* refresh the dist[] and p[][] */
        for (w = 0; w < g->vex_num; w++) {
            if (g->adj_mat[v][w] != 0) {
                if (!finish[w] && (min + g->adj_mat[v][w]) < dist[w]) {
                    dist[w] = min + g->adj_mat[v][w];
                    for (j = 0; j < g->vex_num; j++) {
                        p[w][j] = p[v][j];
                    }
                    p[w][w] = 1;
                }
            }
        }
    }

    for (i = 0; i < g->vex_num; i++) {
        printf("%d ", dist[i]);
    }

    return;
}